#!/usr/bin/env python

from __future__ import generators


class odict ( dict ):
	"""
	Ordered dictionary
	"""

	def __init__ ( self, baseobj = None ):
		"""
		odict ( baseobj = None )

		Builds an ``odict`` instance. If ``baseobj`` is a dictionary the
		odict's contents are copied from the dictionary; if ``baseobj`` is
		a list or a tuple of ``(key, value)`` pairs the odict's contents
		are taken from the pairs (and the order of the keys is preserved).
		"""

		if baseobj:
			super ( odict, self ).__init__ ( baseobj )

			if isinstance ( baseobj, dict ): self._keys = baseobj.keys ()
			elif isinstance ( baseobj, list ) or isinstance ( baseobj, tuple ): self._keys = [ k for ( k, v ) in baseobj ]
		else:
			super ( odict, self ).__init__ ()
			self._keys = []


	def __delitem__ ( self, key ):
		"""
		__delitem__ ( key )

		Removes ``key`` from the dictionary.
		"""

		super ( odict, self ).__delitem__ ( key )
		self._keys.remove ( key )


	def __setitem__ ( self, key, item ):
		"""
		__setitem__ ( key, item )

		Sets ``key`` to ``item``. If ``key`` is a new key it is
		appended at the end of the dictionary.
		"""

		super ( odict, self ).__setitem__ ( key, item )
		if key not in self._keys: self._keys.append ( key )


	def clear ( self ):
		"""
		clear ()

		Removes all items from the dictionary.
		"""

		super ( odict, self ).clear ( self )
		self._keys = []


	def copy ( self ):
		"""
		copy () -> odict

		Returns a (shallow) copy of the dictionary.
		"""

		newodict = odict ()
		newodict.update ( self )
		return newodict


	def items ( self ):
		"""
		items () -> list of ( key, value ) pairs

		Returns a copy of the dictionary list of ( key, value ) pairs ordered
		by key.
		"""

		return [ ( k, self [ k ] ) for k in self._keys ]


	def keys ( self ):
		"""
		keys () -> list

		Returns a copy of the dictionary list of keys (ordered).
		"""

		return self._keys [ : ]


	def values ( self ):
		"""
		values () -> list

		Returns a copy of the dictionary list of values ordered by key.
		"""

		return [ self [ k ] for k in self._keys ]


	def popitem ( self ):
		"""
		popitem () -> ( key, value )

		Removes and returns the last ( key, value ) pair in the dictionary.
		"""

		try:
			key = self._keys [ -1 ]

		except IndexError:
			raise KeyError, 'dictionary is empty'

		val = self [ key ]
		del self [ key ]

		return ( key, val )


	def setdefault ( self, key, failobj = None ):
		"""
		setdefault ( key, failobj = None ) -> value

		If ``key`` is not in the dictionary returns ``failobj`` and sets ``key`` to ``failobj``.
		When ``failobj`` is not provided and ``key`` is not in the dictionary, ``None``
		is returned and ``key`` is set to ``None`` in the dictionary.
		"""

		res = super ( odict, self ).setdefault ( self, key, failobj )
		if key not in self._keys: self._keys.append ( key )
		return res


	def update ( self, otherodict ):
		"""
		update ( otherodict )

		Sets in the dictionary all keys belonging to ``otherodict``. If a key is
		already in the dictionary then its value is replaced. New keys are added
		to the end of the dictionary.
		"""

		super ( odict, self ).update ( self, otherodict )
		for key in otherodict._keys:
			if key not in self._keys: self._keys.append ( key )


	def iterkeys ( self ):
		"""
		iterkeys () -> iterator on keys

		Returns an iterator object over the dictionary's keys.
		"""

		for k in self._keys:
			yield k


	def itervalues ( self ):
		"""
		itervalues () -> iterator in values

		Returns an iterator object over the dictionary's values.
		"""

		for k in self._keys:
			yield self [ k ]


	def iteritems ( self ):
		"""
		iteritems () -> iterator on items

		Returns an iterator object over the dictionary's items (that
		is to say (key, value) pairs).
		"""

		for k in self._keys:
			yield ( k, self [ k ] )


	def __iter__ ( self ):
		"""
		__iter__ () -> iterator on keys

		Implements the default iterator: the iterator on keys.
		"""

		return self.iterkeys ()


if __name__ == '__main__':
########
# TEST #
########

	def test ():
		a = odict ()
		a [ '1' ] = 'q'
		a [ '2' ] = 'w'
		a [ '3' ] = 'e'

		print 'a keys: %s' % a.keys ()
		print 'a values: %s' % a.values ()
		print 'a items: %s' % a.items ()

		b = odict ( [ ( 'a', '1' ), ( 'b', '2' ), ( 'c', '3' ) ] )

		print 'b keys: %s' % b.keys ()
		print 'b values: %s' % b.values ()
		print 'b items: %s' % b.items ()



	test ()
#end test

